\section{Integrate Databases into The Solver}
Separate databases are needed for different types of areas since they contain different information.

\subsection{Databases for Simple Territories}
A simple territories is the simplest form of areas since it only provide moves for the player of that territory, therefore no minimax searches are needed. However, a database for simple territories are necessary because \myem{defective} territories exist (not every empty square in a simple territory is obtainable) and Buro has showed that maximizing the number of moves in a single area is an NP-complete problem \cite{np_amz_buro_2000} (for $n \times n$ boards). Moreover, Tegos also showed that having more queens in a territory could possibly make an originally non-defective territory defective \cite{tegos_thesis_2002}. So we cannot know how much a simple territory worths (if the heuristics cannot fill it completely) without exhaustive searches.

In the solver's perspective, simple territories will always shift the bounds in one direction (lower and upper bound have the same sign). Exact simple territories contribute only an integer (i.e., lower and upper bounds collide, positive for Black and negative for White) for the bounds on the whole board. Thus this integer is all we need to compute when building simple territory databases.

For example, \refFigure{fig:st_query} shows a \mydim{2}{3} simple black territory with only one black queen. It is a defective territory as well since no matter where this queen moves, it has to shoot back, therefore blocking its way to the remaining empty. Without the database, the heuristics returns a bounds of \mybounds{1}{2}, since it cannot guarantee the remaining square is reachable or not; but with the databases, we are sure the bounds are \mybounds{1}{1}.

\begin{figure}[htbp] 
    \centering
    \input{./figures/st_q1_2x3_def}
    \caption{Simple Territory Query, Bounds \mybounds{1}{1}}
    \label{fig:st_query} 
\end{figure}

\subsection{Problems With Blockers}

Blockers occur very often during the search, from a strategic point of view, having blokers provides a player the advantage of both securing his territory-to-be and threatens other parts of the board as well. But how a blocker territory should be queried with the databases can be complex depends on how many blockers it has and what each of the blockers are blocking.

\subsubsection{No Blockers Blocks More Than One Territories}

In its simplest form, a blocker territory is just one queen of one color
blocking off part of the board from his opponent. For example, in
\refFigure{bt_simple_query}, the black queen is a blocker blocking a territory
with only one empty, which gives a bounds of \mybounds{1}{1}. Meanwhile, as
this black blocker is used in filling the blocker territory, it cannot be used
to improve the bounds of the active area; the white queen on the other hand,
can find a move no matter what, so the bounds of the active area
is \mybounds{-2}{0}. Toghther they give a global bounds of \mybounds{-1}{1}.

\begin{figure}[htbp] 
    \centering
    \input{./figures/bt_b1_3x3}
    \caption{Simple Blocker Territory, Global Bounds \mybounds{-1}{1}}
    \label{bt_simple_query}
\end{figure}

As one might have guessed, having blockers for extra partition does not
necessarily guarantee a better bounds. For example, in \refFigure{bt_simple_query}, the
golbal bounds will still be \mybounds{-1}{1} since both players can find a move
regardless who moves first.

\begin{figure}[htbp] 
    \centering
    \input{./figures/bt_malform}
    \caption{Problem with blockers}
    \label{fig:bt_malform}
\end{figure}

Blocker territories in general can get fairly complicated since there is
virtuall no limit to the number of blockers that can present in a blocker
territory other than the number of queens available. For example, even if you
only consider queens directly adjacent to the empties when building a blocker
territory you can have up to 8 blockers in for only one empty square, as shown
in \refFigure{fig:bt_malform}.

\begin{figure}[htbp]
    \centering
    \subfloat[Blockers blocks opponent in the same active areas]{
        \input{./figures/bt_b2_5x4} 
        \label{fig:bt_2_blk_1}
    }
    \hspace{1cm}
    \subfloat[Blockers blocks opponent in different active areas]{
        \input{./figures/bt_b3_6x6} 
        \label{fig:bt_3_blk_1}
    }
\caption{Multiple blockers for one blocker territory} \label{fig:bt_more_blockers} 
\end{figure}

Moreover, blockers in the same blocker territory can block this territory from
opponents in both the same and different active areas. For example,
in \refFigure{fig:bt_2_blk_1} both the two Black blockers belong to the
blocker territory in the upper right corner and both belong to the active area
at the same time; however in \refFigure{fig:bt_3_blk_1}, even though Black
blockers $E5$, $C3$ and $D3$ all block the same territory in the middle, but
$E5$ belongs to the active area in the upper right corner but the other two
belong to the active area in the lower left.

%To make things even more complex, there can be normal queens in blocker territories (e.g., \refFigure{fig:bt_normalqueen}) which could possibly fill most empties in the blocker territory, if not all. Even though more queens are generally considerly more powerful in filling territories, Tegos also showed that more queens can make non-defective territories defective \cite{tegos_thesis_2002}.

%\begin{figure}[htbp] 
%    \centering
%    \input{./figures/bt_normalqueen}
%    \caption{Normal queen $C2$ in the blocker territory}
%    \label{fig:bt_normalqueen}
%\end{figure}

Despite the fact that a blocker territory might get complicated as stated
above, as long as no blockers in this blocker territory blocks territories
other than this one, querying such a position is straight forward, since no
corrections for the blockers involved are necessary.

\subsubsection{All Blockers Blocks More Than One Territories}

If a blocker happens to block off more than one territories simultaneously,
then it can only guarantee the biggest one by walking in it and shooting back
to block the opponent. This process is called \myem{correction}. In bounds
computing, correction is reflected by adding only the lower bound of the
biggest blockerter territory to the bounds for each blocker. For example,
in \refFigure{fig:bt_2_simple_query}, the black blocker is blocking two
territories (providing \mybounds{1}{1} and \mybounds{2}{2} respectively) and
the the active is evaluated as \mybounds{-2}{0} (again, white has at least one
move). So the global bounds is computed as: \mybounds{2-2}{1+2+0}
$=$ \mybounds{0}{3}. A lower global bound of 0 (rather than 1) reflects that
black can move at least as many as white simply by walking into the larger
territory and a upper global bound of 3 means that black can get more moves if
white blunders (but no more than 3).

\begin{figure}[htbp] 
    \centering
    \input{./figures/bt_b1_4x3}
    \caption{Black Blocks Two Territories, Global Bounds \mybounds{0}{3}}
    \label{fig:bt_2_simple_query}
\end{figure}

If more than one blocker in a blocker territory blocks multiple territories,
the querying process becomes problematic since even though we could know
exactly how much this blocker territory worths, but we don't know exactly how
many moves each queen contributes and thus corrections for these blockers
cannot be done correctly. For example, in \refFigure{fig:bt_both_block_more},
apparently the shared blocker territory by the two Black blockers can be
filled completely with either of the queens solely or with them combined.
However when querying, we can only get a bounds of \mybounds{2}{2}, but no
information on who gets what therefore unable perform correction for both queens.

\begin{figure}[htbp]
    \centering
    \input{./figures/bt_b2_5x5}
    \caption{Both Black blockers blocks multiple territories, assigned to $B2$}
    \label{fig:bt_both_block_more}
\end{figure}

Unfortunately, we cannot guess how many moves each blocker could provide nor
tell which blocker can help the most in such a territory without exhaustive
search, so for handling blocker territories with multiple blockers but no
normal queens, we used a simple heuristic shown
in \refFigure{fig:bt_multiple}. First we find out the biggest territory each
blocker blocks except for this one; then we "assign" this territory to the
blocker whose maximun territory is the smallest by marking other blockers as
arrows. Notice that because we have changed the position, if the queried value
is less than the number of empties available in this territory, we are no
longer certain whether this is a defective area or not. This is reflected by
the loosened upper bound if this case happens. The rationale of such a
modification goes that defective territories do not happen a lot during the
search, and this blocker territory should be used to enhance the weakest
blocker. The drawbacks are obvious as well: first, the queens are picked
randomly if they have the same "maximum other territories"; second, we lost
the optimality if the queried result is less than the number of empties in the
territory (i.e., looser bounds).

\begin{figure}[htbp] 
    \centering
    \input{./figures/pseudo_bt_multiple.tex}
    \raggedright
    \footnotesize{* Bounds are shown in Black perspective, negate and switch for White.}
    \caption{Heuristics for blocker territories with more than 1 blockers
    blocking multiple territories}
    \label{fig:bt_multiple}
\end{figure}

For example, in \refFigure{fig:bt_both_block_more} the shared Black blocker
territory will be assigned to $B2$ since it blocks another territory of size 1
but $D2$ blocks another territory of size 2.

\subsubsection{Some Blockers Blocks More Than One Territories}

If both queens that do and donot block multiple territories present at the
same time, we can mark all the queens that do as arrows and query the changed
position. But again, we would have to loose the upper bound if the queried
result is less than the number of empties in the territory.

For example, blocker territory shown in \refFigure{bt_assign_smallest} (delimited by red dashed lines) will be assigned to the black blocker $C2$ since the other two blockers have other territories to block.

\begin{figure}[htbp]
    \centering
    \input{./figures/bt_b3_5x5}
    \caption{Blocker territory assigned to $C2$}
    \label{bt_assign_smallest}
\end{figure}


\subsection{Combinatorial Game Databases for Active Areas}
For active areas, we used the combinatorial database computed by Marcus \mycomm{need reference}.

\begin{itemize}
\item \mybf{Integer} used value at -1.
\item \mybf{Fraction} used value at 0.
\item \mybf{Infinitesimals} used value at -1. \mycomm{these are the fuzzies, am I right?}
\item \mybf{Hot games} used value at 0.
\end{itemize}


